package com.cwj.lab3.博客需要;

import com.cwj.lab1.QueueCy;
import com.cwj.lab1.myArrayList;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Graph_table_2 {
    public static class Node{
        //data这里可以存放数据域
        int inDegree;//如果为有向图就为入度，若为无向图就为度
        //ptr
        private myArrayList<Edge>edgeList;//边表

        public void setInDegree(int inDegree) {
            this.inDegree = inDegree;
        }

        public Node() {
            inDegree=0;
            edgeList=new myArrayList<>();
        }

        public int getInDegree() {
            return inDegree;
        }

        public myArrayList<Edge> getEdgeList() {
            return edgeList;
        }
    }

    public myArrayList<Node> getNodeList() {
        return nodeList;
    }

    public static class Edge{
        int to;//边的尾点
        int val;//权重

        public Edge(int to, int val) {
            this.to = to;
            this.val = val;
        }

        public int getTo() {
            return to;
        }

        public int getVal() {
            return val;
        }
    }
    //邻接表
    private  myArrayList<Node>nodeList;
    //点数
    private int v_num;
    //边数
    private int e_num;
    public void init(int v_num,int e_num){
        this.v_num=v_num;
        this.e_num=e_num;
        this.nodeList=new myArrayList<>(v_num);
        for (int i = 0; i < this.v_num; i++) {
            nodeList.addLast(new Node());
        }
    }
    /**建无向图或是有向图
     * @param isUndirert 确定建哪一种图
     * */
    public void init_undirect(String path,boolean isUndirert){
        int u=0,v=0,val=0;Node nn=null;
        try (Scanner in = new Scanner(new File(path))) {
            this.init(in.nextInt(),in.nextInt());//读入点数，边数
            for (int i = 0; i < this.e_num; i++) {
                u=in.nextInt();v=in.nextInt();val=in.nextInt();
                nn=this.nodeList.get(u);
                nn.edgeList.addLast(new Edge(v,val));
                this.nodeList.get(v).inDegree+=1;
                if(isUndirert)  {this.nodeList.get(v).edgeList.addLast(new Edge(u,val));}
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
    /**
     * 保证这个图的所有结点一定被遍历
     * */
    public int dfs(){
        System.out.println("dfs遍历结果");
        boolean[]vis=new boolean[this.v_num];
        StringBuffer sb=new StringBuffer();
        int num=0;
        for (int i = 0; i < this.v_num; i++) {
            if(vis[i]=false){
                num+=1;
            }
            this.dfs(i,vis,sb);
        }
        return num;
    }
    /**
     * 以statr为起点进行DFS
     * */
    public void dfs(int start){
        System.out.println("~~~~~~~~~~~~~~~~~~~~~~~");
        System.out.println("以结点"+start+"开始dfs遍历结果:");
        boolean[]vis=new boolean[this.v_num];
        StringBuffer sb=new StringBuffer();
        this.dfs(start,vis,sb);
        //System.out.println("~~~~~~~~~~~~~~~~~~~~~~~");

    }
    /**
     * dfs的递归函数，私密，不对用户公开
     * */
    private void dfs(int ind, boolean []vis,StringBuffer sb){
        if(vis[ind]){
            return;
        }
        vis[ind]=(true);
        System.out.println(sb.toString()+ind);
        myArrayList<Edge>nn_edge=this.nodeList.get(ind).edgeList;
        sb.append("  ");
        for (int i = 0; i < nn_edge.size(); i++) {

            dfs(nn_edge.get(i).to,vis,sb);
        }
        sb.deleteCharAt(sb.length()-1);
        sb.deleteCharAt(sb.length()-1);
    }
    public void show(){
        for (int i = 0; i < this.v_num; i++) {
            myArrayList<Edge> list=this.nodeList.get(i).edgeList;
            System.out.print("结点："+i+"-->");
            for (int j = 0; j <list.size(); j++) {
                System.out.print(list.get(j).to+" ");
            }
            System.out.println();
        }
    }

    /**
     * 广度优先搜索
     * */
    public void BFS(int start){
        System.out.println("以"+start+"结点开始进行BFS:");
        boolean[]vis=new boolean[this.v_num];
        QueueCy<Integer>que=new QueueCy<>();
        que.push(start);
        int top=0,tt=0;
        while(!que.isEmpty()){
            top=que.pop();
            vis[top]=true;
            System.out.print(top);
            myArrayList<Edge>list=this.nodeList.get(top).edgeList;
            for (int i = 0; i < list.size(); i++) {
                tt=list.get(i).to;
                if(!vis[tt])
                que.push(tt);
            }
        }
        System.out.println();
    }

    public int getV_num() {
        return v_num;
    }

    public int getE_num() {
        return e_num;
    }

    
    

    public static void main(String[] args) {
        String path="src/src/com/cwj/lab3/博客需要/dfs/dfs测试集";
        Graph_table_2 graph=new Graph_table_2();
        graph.init_undirect(path,false);
//        graph.show();
        for (int i = 0; i < graph.getV_num() ; i++) {
            graph.dfs(i);
        }
        System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        for (int i = 0; i < graph.getV_num(); i++) {
            graph.BFS(i);
        }

    }
}
//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//        以0结点开始进行BFS:
//        01526734
//        以1结点开始进行BFS:
//        126734
//        以2结点开始进行BFS:
//        2346
//        以3结点开始进行BFS:
//        346
//        以4结点开始进行BFS:
//        4
//        以5结点开始进行BFS:
//        5
//        以6结点开始进行BFS:
//        6
//        以7结点开始进行BFS:
//        7